// 单调队列的实现，可以高效维护最大值和最小值
class MonotonicQueue {
  constructor() {
    // 常规队列，存储所有元素
    this.q = [];
    // 元素降序排列的单调队列，头部是最大值
    this.maxq = [];
    // 元素升序排列的单调队列，头部是最小值
    this.minq = [];
  }
  push(elem) {
    // 维护常规队列，直接在队尾插入元素
    this.q.push(elem);

    // 维护 maxq，将小于 elem 的元素全部删除
    while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < elem) {
      this.maxq.pop();
    }
    this.maxq.push(elem);

    // 维护 minq，将大于 elem 的元素全部删除
    while (this.minq.length > 0 && this.minq[this.minq.length - 1] > elem) {
      this.minq.pop();
    }
    this.minq.push(elem);
  }
  max() {
    // maxq 的头部是最大元素
    return this.maxq[0];
  }
  min() {
    // minq 的头部是最大元素
    return this.minq[0];
  }
  pop() {
    // 从标准队列头部弹出需要删除的元素
    var deleteVal = this.q.shift();

    // 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
    if (deleteVal === this.maxq[0]) {
      this.maxq.shift();
    }
    if (deleteVal === this.minq[0]) {
      this.minq.shift();
    }
    return deleteVal;
  }
  size() {
    // 标准队列的大小即是当前队列的大小
    return this.q.length;
  }
  isEmpty() {
    return this.q.length === 0;
  }
}
